import java.util.ArrayList;
import java.util.List;

/**
 * @作者 钟先崟
 * @时间 2023-03-27 9:32
 * @说明 94. 二叉树的中序遍历
 * 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
 * 输入：root = [1,null,2,3]
 * 输出：[1,3,2]
 */
public class Solution {
    /**
     * 执行用时： 0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：40 MB, 在所有 Java 提交中击败了10.16% 的用户
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        search(root.left, list);
        search(root.right, list);
        return list;
    }

    public void search(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            search(root.left, res);
        }
        res.add(root.val);
        if (root.right != null) {
            search(root.right, res);
        }
    }
}
